import random
import math
import matplotlib.pyplot as plt
plt.rcParams["font.family"] = ["SimHei", "WenQuanYi Micro Hei", "Heiti TC"]
plt.rcParams["axes.unicode_minus"] = False  # 解决负号显示问题

# 计算单个点到最近质心的簇索引
def assign_cluster(point, centroids):
    min_dist = float('inf')
    cluster_idx = 0
    for i, cent in enumerate(centroids):
        # 欧氏距离计算（简化写法）
        dist = math.hypot(*[p - c for p, c in zip(point, cent)])
        if dist < min_dist:
            min_dist = dist
            cluster_idx = i
    return cluster_idx

# 主K-Means函数
def Kmeans(data, k, epsilon=1e-3, max_iter=100):
    random.seed(42)
    centroids = random.sample(data, k)

    for _ in range(max_iter):
        clusters = [[] for _ in range(k)]
        labels = []
        for point in data:
            idx = assign_cluster(point, centroids)
            clusters[idx].append(point)
            labels.append(idx)

        new_centroids = []
        for cluster in clusters:
            if not cluster:
                new_cent = random.choice(data)
            else:
                # 按维度求平均
                new_cent = [sum(dim) / len(cluster) for dim in zip(*cluster)]
            new_centroids.append(new_cent)

        total_shift = sum(
            math.hypot(*[c - nc for c, nc in zip(old, new)])
            for old, new in zip(centroids, new_centroids)
        )
        if total_shift < epsilon:
            print(f"迭代{_ + 1}次后收敛")
            break

        centroids = new_centroids
    else:
        print(f"达到最大迭代次数{max_iter}，未完全收敛")

    return centroids, labels


# 测试代码
if __name__ == "__main__":
    true_centers = [[2, 3], [7, 5], [4, 9], [8, 2]]  # 真实质心
    data = []
    for center in true_centers:
        # 每类生成80个点，标准差0.6
        for _ in range(80):
            x = random.gauss(center[0], 0.6)
            y = random.gauss(center[1], 0.6)
            data.append([x, y])

    # 运行K-Means（k=4，与真实簇数匹配）
    k = 4
    final_centers, labels = Kmeans(data, k)

    # 输出结果
    print("\n最终聚类中心（保留2位小数）：")
    for i, cent in enumerate(final_centers):
        print(f"簇{i + 1}: ({cent[0]:.2f}, {cent[1]:.2f})")

    # 可视化聚类结果
    colors = ['red', 'green', 'blue', 'orange']  # 4个簇的颜色
    plt.figure(figsize=(8, 6))
    # 绘制数据点（按标签着色）
    for i, point in enumerate(data):
        plt.scatter(point[0], point[1], c=colors[labels[i]], alpha=0.6, s=30)
    # 绘制最终质心（黑色叉号，放大显示）
    for cent in final_centers:
        plt.scatter(cent[0], cent[1], c='black', marker='x', s=200, linewidths=3)
    # 绘制真实质心（灰色圆圈，用于对比）
    for true_cent in true_centers:
        plt.scatter(true_cent[0], true_cent[1], c='gray', marker='o', s=150,
                    edgecolors='black', facecolors='none', linewidths=2)

    plt.title("K-Means 聚类结果", fontsize=14)
    plt.xlabel("X轴", fontsize=12)
    plt.ylabel("Y轴", fontsize=12)
    plt.legend(["簇1", "簇2", "簇3", "簇4", "最终质心", "真实质心"], loc='best')
    plt.grid(alpha=0.3)
    plt.show()